\documentclass[a4paper, 12pt, titlepage]{article}
\usepackage[cm]{fullpage}
\usepackage[T2A]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[russian]{babel}
\usepackage{times}
\usepackage{cite}
\usepackage{xcolor}
\usepackage[pdftex]{graphicx}
\usepackage{indentfirst}
\usepackage{amsfonts}
\usepackage{longtable}
\usepackage{amsthm}
\usepackage{listings}
\usepackage{amsmath}
\newtheorem{ru_def}{Определение}
\usepackage[pdftex, unicode]{hyperref}
 \hypersetup{
    pdfnewwindow=true,      % links in new window
    colorlinks=true,        % false: boxed links; true: colored links
    linkcolor=black,        % color of internal links
    urlcolor=blue,          % color of external links
    citecolor=black
}

%\usepackage[margin=10pt,font=small,labelfont=bf]{caption}
\usepackage{caption2}
\renewcommand{\captionlabeldelim }{.}

%\renewcommand{\thesection}{\arabic{section}.}

\graphicspath{{pics/}}

\clubpenalty=10000
\widowpenalty=10000

\begin{document}
\sloppy
\section*{Результаты работы адаптивного кодирования}
%Результаты вычислений по шагам выполнения задания.

Было реализовано адаптивное кодирование (варианты A и D) с применением арифметического кодирования.\\

Кодируемая последовательность:
<<Не узнавай друга в три дня, узнавай в три года>>\\

Размер входной последовательности составляет 368 бит.

\subsection*{Результаты применения Adapt-A}
Последовательность, сфомированная кодером:\\

000000000000000000000101011001010111101011111011010100010101001\\
010101010101100010111100110010101101100101110101010010101000000\\
110100101110110011000000000111010100111100001010000110001011010\\
001100000001010000111011011011100010111111001101110010010001100\\
100110010000101111111001001000011100000111010110\\

Длина на выходе: 300 бит.

\subsection*{Результаты применения Adapt-D}
Последовательность, сфомированная кодером:\\

000000000000000000001000000110000011100001111000111110011111110
000000001111111000111001110110101110000010110110001100110011010
011101101001011111001101111100010000010000101100101011000100100
001011001101001001000110100010111100011110010111100011000101000
1010110111110100011010110000010\\

Длина на выходе: 283 бита.

\begin{table}
\caption{Результаты вычислений по шагам алгоритма Adapt-A.}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}\hline
$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\hline
0 & Н & $3.9062500\times 10^{-3}$ & 0 & $1.0000000$ & $3.9062500\times 10^{-3}$\\\hline
1 & е & $3.9215686\times 10^{-3}$ & 0 & $1.0000000$ & $7.6593137\times 10^{-6}$\\\hline
2 &   & $3.9370078\times 10^{-3}$ & $1.2598425\times 10^{-1}$ & $1.0000003$ & $1.0051592\times 10^{-8}$\\\hline
3 & у & $3.9525691\times 10^{-3}$ & 0 & $1.0000003$ & $9.9324039\times 10^{-12}$\\\hline
4 & з & $3.9682539\times 10^{-3}$ & 0 & $1.0000003$ & $7.8828602\times 10^{-15}$\\\hline
5 & н & $3.9840637\times 10^{-3}$ & 0 & $1.0000003$ & $5.2343029\times 10^{-18}$\\\hline
6 & а & $4.0000000\times 10^{-3}$ & 0 & $1.0000003$ & $2.9910302\times 10^{-21}$\\\hline
7 & в & $4.0160642\times 10^{-3}$ & 0 & $1.0000003$ & $1.5015212\times 10^{-24}$\\\hline
8 & а & $1.1111111\times 10^{-1}$ & $7.7777777\times 10^{-1}$ & $1.0000003$ & $1.6683569\times 10^{-25}$\\\hline
9 & й & $4.0322580\times 10^{-3}$ & 0 & $1.0000003$ & $6.7272456\times 10^{-29}$\\\hline
10 &   & $9.0909090\times 10^{-2}$ & $2.7272727\times 10^{-1}$ & $1.0000003$ & $6.1156778\times 10^{-30}$\\\hline
11 & д & $4.0485829\times 10^{-3}$ & 0 & $1.0000003$ & $2.0633191\times 10^{-33}$\\\hline
12 & р & $4.0650406\times 10^{-3}$ & 0 & $1.0000003$ & $6.4519046\times 10^{-37}$\\\hline
13 & у & $7.1428571\times 10^{-2}$ & $3.5714285\times 10^{-1}$ & $1.0000003$ & $4.6085033\times 10^{-38}$\\\hline
14 & г & $4.0816326\times 10^{-3}$ & 0 & $1.0000003$ & $1.2540145\times 10^{-41}$\\\hline
15 & а & $1.2500000\times 10^{-1}$ & $5.6250000\times 10^{-1}$ & $1.0000003$ & $1.5675181\times 10^{-42}$\\\hline
16 &   & $1.1764705\times 10^{-1}$ & $1.7647058\times 10^{-1}$ & $1.0000003$ & $1.8441389\times 10^{-43}$\\\hline
17 & в & $5.5555555\times 10^{-2}$ & $7.2222222\times 10^{-1}$ & $1.0000003$ & $1.0245216\times 10^{-44}$\\\hline
18 &   & $1.5789473\times 10^{-1}$ & $1.5789473\times 10^{-1}$ & $1.0000003$ & $1.6176657\times 10^{-45}$\\\hline
19 & т & $4.0983606\times 10^{-3}$ & 0 & $1.0000003$ & $3.3148888\times 10^{-49}$\\\hline
20 & р & $4.7619047\times 10^{-2}$ & $8.5714285\times 10^{-1}$ & $1.0000003$ & $1.5785185\times 10^{-50}$\\\hline
21 & и & $4.1152263\times 10^{-3}$ & 0 & $1.0000003$ & $2.9527095\times 10^{-54}$\\\hline
22 &   & $1.7391304\times 10^{-1}$ & $1.3043478\times 10^{-1}$ & $1.0000003$ & $5.1351470\times 10^{-55}$\\\hline
23 & д & $4.1666666\times 10^{-2}$ & $7.5000000\times 10^{-1}$ & $1.0000003$ & $2.1396445\times 10^{-56}$\\\hline
24 & н & $4.0000000\times 10^{-2}$ & $4.4000000\times 10^{-1}$ & $1.0000003$ & $8.5585783\times 10^{-58}$\\\hline
25 & я & $4.1322314\times 10^{-3}$ & 0 & $1.0000003$ & $1.3602317\times 10^{-61}$\\\hline
26 & , & $4.1493775\times 10^{-3}$ & $1.7842323\times 10^{-1}$ & $1.0000003$ & $2.0904130\times 10^{-65}$\\\hline
27 &   & $1.7857142\times 10^{-1}$ & $1.0714285\times 10^{-1}$ & $1.0000003$ & $3.7328804\times 10^{-66}$\\\hline
28 & у & $6.8965517\times 10^{-2}$ & $3.1034482\times 10^{-1}$ & $1.0000003$ & $2.5744003\times 10^{-67}$\\\hline
29 & з & $3.3333333\times 10^{-2}$ & $4.0000000\times 10^{-1}$ & $1.0000003$ & $8.5813344\times 10^{-69}$\\\hline
30 & н & $6.4516129\times 10^{-2}$ & $4.5161290\times 10^{-1}$ & $1.0000003$ & $5.5363447\times 10^{-70}$\\\hline
31 & а & $9.3750000\times 10^{-2}$ & $5.3125000\times 10^{-1}$ & $1.0000003$ & $5.1903232\times 10^{-71}$\\\hline
32 & в & $6.0606060\times 10^{-2}$ & $6.3636363\times 10^{-1}$ & $1.0000003$ & $3.1456504\times 10^{-72}$\\\hline
33 & а & $1.1764705\times 10^{-1}$ & $5.0000000\times 10^{-1}$ & $1.0000003$ & $3.7007652\times 10^{-73}$\\\hline
34 & й & $2.8571428\times 10^{-2}$ & $7.1428571\times 10^{-1}$ & $1.0000003$ & $1.0573614\times 10^{-74}$\\\hline
35 &   & $1.6666666\times 10^{-1}$ & $8.3333333\times 10^{-2}$ & $1.0000003$ & $1.7622691\times 10^{-75}$\\\hline
36 & в & $8.1081081\times 10^{-2}$ & $6.2162162\times 10^{-1}$ & $1.0000003$ & $1.4288668\times 10^{-76}$\\\hline
37 &   & $1.8421052\times 10^{-1}$ & $7.8947368\times 10^{-2}$ & $1.0000003$ & $2.6321232\times 10^{-77}$\\\hline
38 & т & $2.5641025\times 10^{-2}$ & $8.9743589\times 10^{-1}$ & $1.0000003$ & $6.7490338\times 10^{-79}$\\\hline
39 & р & $5.0000000\times 10^{-2}$ & $8.0000000\times 10^{-1}$ & $1.0000003$ & $3.3745169\times 10^{-80}$\\\hline
40 & и & $2.4390243\times 10^{-2}$ & $9.2682926\times 10^{-1}$ & $1.0000003$ & $8.2305291\times 10^{-82}$\\\hline
41 &   & $1.9047619\times 10^{-1}$ & $7.1428571\times 10^{-2}$ & $1.0000003$ & $1.5677198\times 10^{-82}$\\\hline
42 & г & $2.3255813\times 10^{-2}$ & $8.3720930\times 10^{-1}$ & $1.0000003$ & $3.6458600\times 10^{-84}$\\\hline
43 & о & $4.1666666\times 10^{-3}$ & 0 & $1.0000003$ & $3.4525190\times 10^{-88}$\\\hline
44 & д & $4.4444444\times 10^{-2}$ & $6.8888888\times 10^{-1}$ & $1.0000003$ & $1.5344528\times 10^{-89}$\\\hline
45 & а & $1.0869565\times 10^{-1}$ & $4.3478260\times 10^{-1}$ & $1.0000003$ & $1.6678835\times 10^{-90}$\\\hline
\end{tabular}
\end{center}
\end{table}

\begin{table}
\caption{Результаты вычислений по шагам алгоритма Adapt-D.}
\begin{center}
\begin{tabular}{|l|l|l|l|l|l|}\hline
$i$ & $x_i$ & $p(x_i)$ & $q(x_i)$ & $F$ & $G$ \\\hline
0 & Н & $3.9062500\times 10^{-3}$ & 0 & $1.0000000$ & $3.9062500\times 10^{-3}$\\\hline
1 & е & $3.9215686\times 10^{-3}$ & 0 & $1.0000000$ & $7.6593137\times 10^{-6}$\\\hline
2 &   & $3.9370078\times 10^{-3}$ & $1.2598425\times 10^{-1}$ & $1.0000004$ & $1.5077389\times 10^{-8}$\\\hline
3 & у & $3.9525691\times 10^{-3}$ & 0 & $1.0000004$ & $2.9797211\times 10^{-11}$\\\hline
4 & з & $3.9682539\times 10^{-3}$ & 0 & $1.0000004$ & $5.9121452\times 10^{-14}$\\\hline
5 & н & $3.9840637\times 10^{-3}$ & 0 & $1.0000004$ & $1.1777181\times 10^{-16}$\\\hline
6 & а & $4.0000000\times 10^{-3}$ & 0 & $1.0000004$ & $2.3554363\times 10^{-19}$\\\hline
7 & в & $4.0160642\times 10^{-3}$ & 0 & $1.0000004$ & $4.7297918\times 10^{-22}$\\\hline
8 & а & $6.2500000\times 10^{-2}$ & $8.7500000\times 10^{-1}$ & $1.0000004$ & $2.9561199\times 10^{-23}$\\\hline
9 & й & $4.0322580\times 10^{-3}$ & 0 & $1.0000004$ & $5.2977059\times 10^{-26}$\\\hline
10 &   & $5.0000000\times 10^{-2}$ & $5.5000000\times 10^{-1}$ & $1.0000004$ & $2.6488529\times 10^{-27}$\\\hline
11 & д & $4.0485829\times 10^{-3}$ & 0 & $1.0000004$ & $4.3871322\times 10^{-30}$\\\hline
12 & р & $4.0650406\times 10^{-3}$ & 0 & $1.0000004$ & $7.4307795\times 10^{-33}$\\\hline
13 & у & $3.8461538\times 10^{-2}$ & $6.1538461\times 10^{-1}$ & $1.0000004$ & $2.8579921\times 10^{-34}$\\\hline
14 & г & $4.0816326\times 10^{-3}$ & 0 & $1.0000004$ & $4.5827862\times 10^{-37}$\\\hline
15 & а & $1.0000000\times 10^{-1}$ & $7.3333333\times 10^{-1}$ & $1.0000004$ & $4.5827862\times 10^{-38}$\\\hline
16 &   & $9.3750000\times 10^{-2}$ & $4.3750000\times 10^{-1}$ & $1.0000004$ & $4.2963620\times 10^{-39}$\\\hline
17 & в & $2.9411764\times 10^{-2}$ & $8.5294117\times 10^{-1}$ & $1.0000004$ & $1.2636359\times 10^{-40}$\\\hline
18 &   & $1.3888888\times 10^{-1}$ & $3.8888888\times 10^{-1}$ & $1.0000004$ & $1.7550498\times 10^{-41}$\\\hline
19 & т & $4.0983606\times 10^{-3}$ & 0 & $1.0000004$ & $2.2714191\times 10^{-44}$\\\hline
20 & р & $2.5000000\times 10^{-2}$ & $9.2500000\times 10^{-1}$ & $1.0000004$ & $5.6785479\times 10^{-46}$\\\hline
21 & и & $4.1152263\times 10^{-3}$ & 0 & $1.0000004$ & $7.2331102\times 10^{-49}$\\\hline
22 &   & $1.5909090\times 10^{-1}$ & $3.6363636\times 10^{-1}$ & $1.0000004$ & $1.1507220\times 10^{-49}$\\\hline
23 & д & $2.1739130\times 10^{-2}$ & $8.4782608\times 10^{-1}$ & $1.0000004$ & $2.5015697\times 10^{-51}$\\\hline
24 & н & $2.0833333\times 10^{-2}$ & $6.0416666\times 10^{-1}$ & $1.0000004$ & $5.2116036\times 10^{-53}$\\\hline
25 & я & $4.1322314\times 10^{-3}$ & 0 & $1.0000004$ & $6.0299546\times 10^{-56}$\\\hline
26 & , & $4.1493775\times 10^{-3}$ & $1.7842323\times 10^{-1}$ & $1.0000004$ & $7.2174688\times 10^{-59}$\\\hline
27 &   & $1.6666666\times 10^{-1}$ & $3.3333333\times 10^{-1}$ & $1.0000004$ & $1.2029114\times 10^{-59}$\\\hline
28 & у & $5.3571428\times 10^{-2}$ & $5.1785714\times 10^{-1}$ & $1.0000004$ & $6.4441685\times 10^{-61}$\\\hline
29 & з & $1.7241379\times 10^{-2}$ & $5.8620689\times 10^{-1}$ & $1.0000004$ & $1.1110635\times 10^{-62}$\\\hline
30 & н & $5.0000000\times 10^{-2}$ & $6.1666666\times 10^{-1}$ & $1.0000004$ & $5.5553177\times 10^{-64}$\\\hline
31 & а & $8.0645161\times 10^{-2}$ & $6.7741935\times 10^{-1}$ & $1.0000004$ & $4.4800949\times 10^{-65}$\\\hline
32 & в & $4.6875000\times 10^{-2}$ & $7.6562500\times 10^{-1}$ & $1.0000004$ & $2.1000445\times 10^{-66}$\\\hline
33 & а & $1.0606060\times 10^{-1}$ & $6.3636363\times 10^{-1}$ & $1.0000004$ & $2.2273199\times 10^{-67}$\\\hline
34 & й & $1.4705882\times 10^{-2}$ & $8.2352941\times 10^{-1}$ & $1.0000004$ & $3.2754704\times 10^{-69}$\\\hline
35 &   & $1.5714285\times 10^{-1}$ & $2.5714285\times 10^{-1}$ & $1.0000004$ & $5.1471679\times 10^{-70}$\\\hline
36 & в & $6.9444444\times 10^{-2}$ & $7.3611111\times 10^{-1}$ & $1.0000004$ & $3.5744221\times 10^{-71}$\\\hline
37 &   & $1.7567567\times 10^{-1}$ & $2.4324324\times 10^{-1}$ & $1.0000004$ & $6.2793902\times 10^{-72}$\\\hline
38 & т & $1.3157894\times 10^{-2}$ & $9.4736842\times 10^{-1}$ & $1.0000004$ & $8.2623556\times 10^{-74}$\\\hline
39 & р & $3.8461538\times 10^{-2}$ & $8.7179487\times 10^{-1}$ & $1.0000004$ & $3.1778290\times 10^{-75}$\\\hline
40 & и & $1.2500000\times 10^{-2}$ & $9.6250000\times 10^{-1}$ & $1.0000004$ & $3.9722863\times 10^{-77}$\\\hline
41 &   & $1.8292682\times 10^{-1}$ & $2.1951219\times 10^{-1}$ & $1.0000004$ & $7.2663774\times 10^{-78}$\\\hline
42 & г & $1.1904761\times 10^{-2}$ & $8.9285714\times 10^{-1}$ & $1.0000004$ & $8.6504493\times 10^{-80}$\\\hline
43 & о & $4.1666666\times 10^{-3}$ & 0 & $1.0000004$ & $6.7057747\times 10^{-83}$\\\hline
44 & д & $3.4090909\times 10^{-2}$ & $7.7272727\times 10^{-1}$ & $1.0000004$ & $2.2860595\times 10^{-84}$\\\hline
45 & а & $1.0000000\times 10^{-1}$ & $5.4444444\times 10^{-1}$ & $1.0000004$ & $2.2860595\times 10^{-85}$\\\hline
\end{tabular}
\end{center}
\end{table}

\newpage
\section*{Реализация адаптивного кодирования с применением арифметического кодирования}

\begin{lstlisting}

public class AdaptiveArithmeticCoding {
	public static String code(byte[] x, boolean isDCoding) 
		throws UnsupportedEncodingException {
        final Fraction ONE = new Fraction(1, 1);
        final Fraction ZERO = new Fraction(0, 1);
		Fraction F = ZERO;
		Fraction G = ONE;

        Map<Byte, Integer> index = new HashMap<Byte, Integer>();
        List<Fraction> p = new ArrayList<Fraction>(257);
        List<Fraction> q = new ArrayList<Fraction>(257);
        List<Byte> symbols = new ArrayList<Byte>(256);

        p.add(ONE);
        q.add(ONE);

        int[] tau = new int[256];
       
		for (int i = 0; i < x.length; i++) {
            byte curr = x[i];
                       
            if (!index.containsKey(curr)) {
                //Writing escape
                F = F.add(G.multiply(q.get(0)));
                G = G.multiply(p.get(0));

                int myPosition = 0;
                for (byte s = 0; s < curr; ++s) {
                    if (!index.containsKey(s)) {
                        ++myPosition;
                    }
                }
                int mn = symbols.size();
                Fraction myP, myQ;
                myP = new Fraction(1, 256 - mn);
                myQ = new Fraction(myPosition, 256 - mn);

                //Writing the new symbol
                F = F.add(G.multiply(myQ));
                G = G.multiply(myP);

                p.add(null);
                q.add(null);
                index.put(curr, index.size() + 1);
                symbols.add(curr);
            } else {
                int code = index.get(curr);
                F = F.add(G.multiply(q.get(code)));
                G = G.multiply(p.get(code));
            }
         
            tau[curr & 255]++;

            int mn = symbols.size();
            int n = i + 1;

            if (isDCoding) {
                p.set(0, new Fraction(mn, 2 * n));
            } else {
                p.set(0, new Fraction(1, n + 1));
            }
            q.set(0, ZERO);

            for (int t = 0; t < mn; ++t) {
                byte b = symbols.get(t);
                if (isDCoding) {
                    p.set(t + 1, new Fraction(2 * tau[b & 255] - 1, 2 * n));
                } else {
                    p.set(t + 1, new Fraction(tau[b & 255], n + 1));
                }
                q.set(t + 1, q.get(t).add(p.get(t)));
            }
		}

        Fraction value = F.add(G.multiply(new Fraction(1, 2)));
		int z = G.inverse().log2up() + 1;
        StringBuilder result = new StringBuilder();
		String out = value.nBitsAfterComma(z).toString(2);
		while (result.length() + out.length() < z) {
            result.append("0");
		}
        result.append(out);
        return result.toString();
	}
	
	public static void main (String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader
			(new FileInputStream("input.txt"), "cp1251"));
        String input = in.readLine();
        in.close();
		String output = code(input.getBytes("cp1251"), true);
		System.out.println(output);
	}
\end{lstlisting}

\end{document} 